
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>

#define LIST_SIZE 1000


typedef struct _hash_list {
    int data;
    struct _hash_list *sub_list;
}hash_list_t;

hash_list_t *table[LIST_SIZE];

bool containsDuplicate(int* nums, int numsSize) {
    memset(table, NULL, sizeof(hash_list_t *) * LIST_SIZE);

    for (int i = 0; i < numsSize; i++)
    {
        if (table[nums[i] % LIST_SIZE] == NULL) {
            hash_list_t *list = (hash_list_t *)malloc(sizeof(hash_list_t));
            if (!list)
                return false;
            list->data = nums[i];
            list->sub_list = NULL;
            table[nums[i] % LIST_SIZE] = list;
        } else {
            hash_list_t *list = table[nums[i] % LIST_SIZE];
            hash_list_t *prev = NULL;

            while(list) {
                if (list->data == nums[i])
                    return true;

                prev = list;
                list = list->sub_list;
            }

            hash_list_t *tmp = (hash_list_t *)malloc(sizeof(hash_list_t));
            if (!tmp)
                return false;
            tmp->data = nums[i];
            tmp->sub_list = NULL;
            prev->sub_list = tmp;
        }
    }

    return false;
}

int hammingWeight(uint32_t n) {

    int ret = 0;

    while (n > 0)
    {
        if (n & 1)
            ret++;
        n = n >> 1;
    }

    return ret;
}
int main(int argc, char *argv[])
{
    int list[11] = {1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 10};
    fprintf(stdout, "duplicated result is...\n");
    fprintf(stdout, "result is %d\n", containsDuplicate(list, 11));

    fprintf(stdout, "hamming weight is %d\n", hammingWeight(1));

    return 0;
}
